/* * @Author: Mohan Li  * @Date: 2020-12-28 14:19:03   */
import java.util.ArrayList;

class PriorityQueue {
    ArrayList<Integer> heap;

    //Constructor
    public PriorityQueue() {
        heap = new ArrayList<>();
    }

    public PriorityQueue(int[] qs) {
        heap = new ArrayList<>();
        for (int q : qs) {
            insert(q);
        }
    }

    //get index of parent leftChild and rightChild
    private int parent(int i) {
        return (i - 1) / 2;
    }

    private int leftChild(int i) {
        return ((2 * i) + 1);
    }

    private int rightChild(int i) {
        return ((2 * i) + 2);
    }

    private void swap(int i1, int i2) {
        int temp = heap.get(i1);
        heap.set(i1, heap.get(i2));
        heap.set(i2, temp);
    }

    private boolean isLeaf(int i) {
        return (2 * i + 1 > heap.size() - 1 && 2 * i + 2 > heap.size() - 1);
    }

    //insert
    public void insert(int q) {
        heap.add(q);
        int i = heap.size() - 1;
        while (heap.get(parent(i)) > heap.get(i)) {
            swap(parent(i), i);
            i = parent(i);
        }
    }

    //deleteMin
    public void deleteMin() {
        int z = heap.get(heap.size() - 1);
        //store the key of z at the root
        heap.set(0, z);
        //delete z
        int size = heap.size();
        heap.remove(size - 1);
        //make sure heap is a binary heap
        rootFix();
    }

    private void rootFix() {
        int minIndex = 0;
        if(heap.get(minIndex)<heap.get(leftChild(minIndex))&&heap.get(minIndex)<heap.get(rightChild(minIndex)))
            return;
        while (true) {
            // jump out of the loop when minIndex reach the leaf
            if (isLeaf(minIndex)) break;
            //in case that right child doesn't exist
            if (leftChild(minIndex) == heap.size() - 1) {
                if (heap.get(heap.size() - 1) < heap.get(minIndex)) {
                    swap(heap.size() - 1, minIndex);
                }
                break;
            }
            // when left child and right child are greater than min, jump out of the loop
            if (heap.get(leftChild(minIndex)) > heap.get(minIndex) && heap.get(rightChild(minIndex)) > heap.get(minIndex))
                break;
            //left child
            int lc = leftChild(minIndex);
            if (lc <= heap.size() - 1 && heap.get(lc) < heap.get(minIndex)) {
                swap(lc, minIndex);
                minIndex = lc;
                continue;
            }
            //right child
            int rc = rightChild(minIndex);
            if (rc <= heap.size() - 1 && heap.get(rc) < heap.get(minIndex)) {
                swap(rc, minIndex);
                minIndex = rc;

            }
        }
        rootFix();
    }
}

class test_priority_queue {
    public static void main(String[] args) {
        //first constructor
        PriorityQueue pq = new PriorityQueue();
        pq.insert(1);
        pq.insert(2);
        pq.insert(45);
        pq.insert(23);
        pq.insert(17);
        pq.insert(12);
        System.out.println(pq.heap);
        pq.deleteMin();
        System.out.println("DeleteMin : " + pq.heap);
        //second constructor
        //int [] qs = {3,10,4,13,21,19,5,25,51,42,48,23};
        int[] qs = {16, 25, 4, 29, 9, 26, 14, 23, 19, 1, 8};
        PriorityQueue pq1 = new PriorityQueue(qs);
        System.out.println(pq1.heap);
        // pq1.deleteMin();
        // System.out.println("DeleteMin : " + pq1.heap);
    }
}